package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author gy
 * @date 2023/04
 */
public class Test0413_01 {

    class MedianFinder {

        /**
         * https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solutions/1142987/dai-tu-xiang-jie-jian-zhi-offer-41-shu-j-y3d6/
         *
         * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
         * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
         *
         * 例如，
         *
         * [2,3,4] 的中位数是 3
         *
         * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
         *
         * 设计一个支持以下两种操作的数据结构：
         *
         * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
         * double findMedian() - 返回目前所有元素的中位数。
         * 示例 1：
         *
         * 输入：
         * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]   调用的函数
         * [[],[1],[2],[],[3],[]]  入参
         * 输出：[null,null,null,1.50000,null,2.00000]  返回值
         * 示例 2：
         *
         * 输入：
         * ["MedianFinder","addNum","findMedian","addNum","findMedian"]
         * [[],[2],[],[3],[]]
         * 输出：[null,null,2.00000,null,2.50000]
         *
         *
         *  Your MedianFinder object will be instantiated and called as such:
         *  MedianFinder obj = new MedianFinder();
         *  obj.addNum(num);
         *  double param_2 = obj.findMedian();
         *
         */
        /** initialize your data structure here. */
        /*
        平衡堆:大顶堆+小顶堆(参考k神)
        创建两个堆:其中堆A为小顶堆(存储较大的一半元素);堆B为大顶堆(存储较小的一半元素)
        规定存储元素个数:A>=B;设A中有m个元素,B中有n个元素,一共有N=m+n个元素
        当N为奇数时:m=(N+1)/2,m=(N-1)/2;当N为偶数时:m=n=N/2
        findMedian():
            1.当m+n为偶数时,中位数=(A堆顶元素+B堆顶元素)/2.0
            2.当m+n为奇数时,中位数=A堆顶元素
        addNum(int num):其目的是使得两个堆平衡(数目差0或1)
            1.当m=n时,num应该添加进A中,但num可能是较小的一半,因此先入堆B,再将B堆顶弹出入A
            2.当m=n+1时,num应该添加进B中,但num可能是较大的一半,因此先入堆A,再将A堆顶弹出入B
            时间复杂度:O(1)+O(logN)=O(logN);空间复杂度:O(N)
        */
        // 声明两个堆
        PriorityQueue<Integer> A, B;
        public MedianFinder() {
            // 初始化堆:A为小顶堆,存储较大的一半元素;B为大顶堆,存储较小的一半元素
            // 默认为小顶堆
            A = new PriorityQueue<>();
//            B = new PriorityQueue<>((a, b) -> b - a);
            // 在整数相减溢出的时候，下面这个测试用例就不正确了：
            // ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[-2147483648],[2],[],[3],[]] 建议改成
            B = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶堆，保存较小的一半
        }

        /*
        添加元素到数据流中
        */
        public void addNum(int num) {
            if(A.size() == B.size()) {
                // 1.m=n,num应该加入A(先入B再弹出B堆顶入A)
                B.add(num);
                A.add(B.poll());
            }else {
                // 2.m=n+1,num应该加入B(先入A再弹出A堆顶入B)
                A.add(num);
                B.add(A.poll());
            }
        }

        /*
        获取数据流的中位数
        */
        public double findMedian() {
            // 注意这里是peek()不是poll()
            return A.size() == B.size() ? (A.peek() + B.peek()) / 2.0 : (double)A.peek();
        }
    }

    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */


    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
